package com.multimedia.scala.euler

import scala.annotation.tailrec
/*
 A common security method used for online banking is to ask the user for three random characters
 from a passcode. For example, if the passcode was 531278, they may ask for the 2nd, 3rd, and
 5th characters; the expected reply would be: 317.
 
 Given that the three characters are always asked for in order, analyse the file so as to
 determine the shortest possible secret passcode of unknown length.
 */
object Asd79 {
  def main(args : Array[String]) : Unit = {
    val passLetters = Array(
        319, 680, 180, 690, 129, 620, 762, 689, 762, 318,
        368, 710, 720, 710, 629, 168, 160, 689, 716, 731,
        736, 729, 316, 729, 729, 710, 769, 290, 719, 680,
        318, 389, 162, 289, 162, 718, 729, 319, 790, 680,
        890, 362, 319, 760, 316, 729, 380, 319, 728, 716)
        
    def findFirst(base: Array[Array[Int]], possible: Set[Int]): Set[Int] = {
      possible.filter(x=>{
        !base.exists(_.tail.exists(_==x))
      })
    }

    def findLast(base: Array[Array[Int]], possible: Array[Int]): Array[Int] = {
      possible.filter(x=>{
        !base.exists(_.reverse.tail.exists(_==x))
      })
    }
    /** finds possible digits */
    def findDigits(base: Array[Array[Int]]): Set[Int] = {
      (0 to 9).filter(x=>{
        base.exists(_.exists(_==x))
      }).toSet
    }

    def checkSequence(base: Array[Array[Int]], num: Array[Int], possible: Set[Int]): Boolean = {
      @tailrec
      def checkSeq(rest: Array[Array[Int]]): Boolean = {
        @tailrec
        def checkCombination(arr: Array[Int]): Boolean = {
          if (arr.isEmpty) return true
          val firstIndex = num.indexOf(arr.head)
          if (!arr.tail.forall(num.indexOf(_, firstIndex)>0)) return false
          checkCombination(arr.tail)
        }
        if (rest.isEmpty) true
        else{
          if (!checkCombination(rest.head)) false 
          else checkSeq(rest.tail)
        }
      }
      //possible.filter(!num.contains(_)).foreach(print(_))
      //println
      possible.filter(!num.contains(_)).size==0&&checkSeq(base)
    }
    
    def findNext(base: Array[Array[Int]], x: Int, possible: Set[Int], num: Array[Int]): Boolean = {
      //current.filter(x=>{
        //if (num.size>10) return false
        if (checkSequence(base, num, possible)) {
        	num.foreach(print(_))
        	//println(x)
        	return true
        }
        possible.foreach(y=>{
          if (findNext(base, y, possible-y, num:+x)) return true
        })
        false
      //})
    }
        
    var digits = passLetters.distinct.map(_.toString.toCharArray.map(_.asDigit))
    var possible = findDigits(digits)
    findFirst(digits, possible).foreach(
    	findNext(digits, _, possible, Array())
    )
  }
}
